<!DOCTYPE group PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<group>

<p>The distance transform of an image <code>image</code> is defined
  as</p>

<pre>
  dt(u,v) = min  image(u',v') + alpha (u'-u-u0)^2 + beta (v'-v'-v0)^2
            u'v'
</pre>

<p>The most common use of the image distance transform is to propagate
the response of a feature detector to nearby image locations. This is
used, for example, in the implementation of certain deformable part
models or the computation of the Chamfer distance. In this tutorial,
the image distance transform is used to compute the distance of each
image pixel to the nearest element in an edge map, obtained from the
Canny's edge detector. The code of this tutorial is located in the
VLFeat folder in <code>toolbox/demo/vl_demo_imdisttf.m</code>.</p>

<p><b>VLFeat</b> implements the fast distance transform algorithm of
Felzenszwalb and Huttelnocher <a href="#ref1">[1]</a>, which has a
linear time complexity in the number of image pixels.</p>

<p>Consider the edge map extracted by the MATLAB built-in Canny edge
detector on one of VLFeat test images:</p>

<precode type="matlab">
im = vl_impattern('roofs1') ;
im = im(1:100,1:100,:) ;
imSize = [size(im,1) size(im,2)] ;
edges = zeros(imSize) + inf;
edges(edge(rgb2gray(im), 'canny')) = 0 ;
</precode>

<div class="figure">
 <img src="%pathto:root;demo/imdisttf_src.jpg"/>
 <img src="%pathto:root;demo/imdisttf_edge.jpg"/>
 <div class="caption">
  <span class="content">
   <b>Left:</b> A detail of the source image. <b>Right:</b> Extracted
   Canny edges. Figure generated by <code>vl_demo_imdisttf</code>.
  </span>
 </div>
</div>

<p>The edge map is preprocessed to assign value <code>-inf</code> to
the pixels that do not contain an edge element and <code>o</code> to
the pixels that do. In this way, the distance transform of the image
has for each pixel the distance to the nearest edge element, provided
that one chooses <code>alpha=beta=1</code> and <code>v0=u0=0</code> in
the definition. Since these are the default values for VLFeat
implementations, the result an be computed by</p>

<precode type="matlab">
[distanceTransform, neighbors] = vl_imdisttf(single(edges)) ;
</precode>

<p>The matrix <code>neighbors</code> contains for each
pixel <code>(u,v)</code> the index of the pixel <code>(u',v')</code>
where the maximum is attained in the definition of the distance
transform. This allows to associate to know for each pixel which is
the nearest edge element, not just its distance, as exemplified by the
following figure:</p>

<div class="figure">
 <img src="%pathto:root;demo/imdisttf_dist.jpg"/>
 <img src="%pathto:root;demo/imdisttf_neigh.jpg"/>
 <div class="caption">
  <span class="content">
   The distance <code>sqrt(distanceTransform)</code> to the closest
   edge element (left) and arrows connecting pixels to their closest
   edge element (right). Figure generated
   by <code>vl_demo_imdisttf</code>.
  </span>
 </div>
</div>


<h1>References</h1>
<ul>
  <li><p id="ref1">[1] P. F. Felzenszwalb and
      D. P. Huttenlocher. Distance transforms of sampled
      functions. Technical report, Cornell University, 2004.</p></li>
</ul>

</group>
